//1.腐烂的苹果 (BFS)
//2.单词搜索  (DFS)
//3.与女生的最短距离
class Solution {
public:
    int arr_x[4] = {-1,1,0,0};
    int arr_y[4] = {0,0,-1,1};
    bool arr_judge[1000][1000] = {false}; //为了不改变grid而引入的
    int rotApple(vector<vector<int> >& grid) {
        int n = grid.size();
        int m = grid[0].size();
        queue<pair<int,int>> q;
        for(int i = 0;i < n;++i){  //刚开始将腐烂的苹果push进q中
            for(int j = 0;j < m;++j){
                if(grid[i][j] == 2){
                    q.push({i,j});
                }
            }
        }
        int res = 0;
        while(!q.empty())
        {
            int size = q.size();
            ++res;
            while(size--)
            {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for(int i = 0;i < 4;++i){
                    int newX = x + arr_x[i];
                    int newY = y + arr_y[i];
                    if(newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1 && !arr_judge[newX][newY]){
                        arr_judge[newX][newY] = true;
                        q.push({newX,newY});
                    }
                }
            }
        }
        for(int i = 0;i < n;++i){
            for(int j = 0;j < m;++j){
                if(grid[i][j] == 1 && !arr_judge[i][j]){
                    return -1;
                }
            }
        }
        return res-1; //注意这里需要减一，因为最后一次并没有感染其他正常的苹果而是检查
    }
};

//2.
class Solution {
public:
    int arr_x[4] = {-1,1,0,0};
    int arr_y[4] = {0,0,-1,1};
    bool arr_judge[6][6] = {false};
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0;i < board.size();++i){
            for(int j = 0;j < board[0].size();++j){
                if(board[i][j] == word[0]){
                    if(dfs(board,word,i,j,0)){
                    return true;
                }
                }
            }
        }
        return false;
    }
    bool dfs(const vector<vector<char>>& board,const string& word,int i,int j,int pos)
    {
        if(pos == word.length()-1){
            return true;
        }
        arr_judge[i][j] = true;
        for(int k = 0;k < 4;++k){
            int x = i + arr_x[k];
            int y = j + arr_y[k]; //注意
            if(x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && !arr_judge[x][y] && board[x][y] == word[pos+1]){
                if(dfs(board,word,x,y,pos+1)){
                    return true;
                }
            }
        }
        arr_judge[i][j] = false;
        return false;
    }
};


vector<vector<int>> shortestDistance(vector<vector<int>>& matrix) {
	int rows = matrix.size();
	int cols = matrix[0].size();
	vector<vector<int>> result(rows, vector<int>(cols, INT_MAX));
	queue<pair<int, int>> q;

	// 找到所有女生的位置并将其距离设为 0
	for (int i = 0; i < rows; ++i) {
		for (int j = 0; j < cols; ++j) {
			if (matrix[i][j] == 1) {
				result[i][j] = 0;
				q.push({ i, j });
			}
		}
	}

	vector<pair<int, int>> directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

	// BFS 遍历
	while (!q.empty()) {
		auto p = q.front();
		q.pop();
		for (const auto& e : directions) {
			int newX = p.first + e.first;
			int newY = p.second + e.second;
			if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && result[newX][newY] > result[p.first][p.second] + 1) {
				result[newX][newY] = result[p.first][p.second] + 1;
				q.push({ newX, newY });
			}
		}
	}

	return result;
}

int main() {
	vector<vector<int>> matrix = {
		{0, 0, 0},
		{0, 1, 0},
		{0, 0, 0}
	};

	vector<vector<int>> distances = shortestDistance(matrix);

	// 输出结果
	for (const auto& row : distances) {
		for (int dist : row) {
			cout << dist << " ";
		}
		cout << endl;
	}

	return 0;
}